package luogu.GraphTheory;
//P3371 【模板】单源最短路径（弱化版
//要换快读不然mle
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2023/1/7 15:22
 */
public class SingleSourceShortestPaths{
    static int N=10005,M=500010;
    static int[]h=new int[N];
    static int[]w=new int[M];
    static int[]e=new int[M];
    static int[]ne=new int[M];
    static int n,m,s,idx;
    static int[]dist=new int[N];
    static Queue<Integer> queue=new ArrayDeque<>();
//    static PriorityQueue<int[]> queue = new PriorityQueue<>((a, b)->{return a[1] - b[1];});
    static boolean[]st=new boolean[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        s=sc.nextInt();
        Arrays.fill(h,-1);
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int c=sc.nextInt();
            add(a,b,c);
        }
        spfa();
        //Dijkstra();
        for(int i=1;i<=n;i++) {
            if(dist[i]==0x3f3f3f3f) {
                System.out.print(Integer.MAX_VALUE+" ");
                continue;
            }
            System.out.print(dist[i]+" ");
        }

    }
    public static void add(int a,int b,int c){
        e[idx]=b;
        ne[idx]=h[a];
        w[idx]=c;
        h[a]=idx++;
    }
    public static void spfa(){
        Arrays.fill(dist,0x3f3f3f3f);
        queue.add(s);
        st[s]=true;
        dist[s]=0;
        while (!queue.isEmpty()){
            int remove = queue.remove();
            st[remove]=false;
            for (int i = h[remove]; i != -1; i=ne[i]) {
                int j=e[i];
                if(dist[j]>dist[remove]+w[i]){
                    dist[j]=dist[remove]+w[i];
                    if(!st[j]){
                        queue.add(j);
                        st[j]=true;
                    }
                }
            }
        }
    }
//    public static void Dijkstra(){
//        Arrays.fill(dist,0x3f3f3f3f);
//        queue.offer(new int[]{s,0});
//        dist[s]=0;
//        while (!queue.isEmpty()){
//            int[] poll = queue.poll();
//            int t=poll[0];
//            int distmin=poll[1];
//            if(st[t]){
//                continue;
//            }
//            st[t]=true;
//            for (int i = h[t]; i != -1; i=ne[i]) {
//                int j=e[i];
//                if(dist[j]>distmin+w[i]){//如果存储的距离大小大于本节点到j节点的距离的话更新
//                    dist[j]=distmin+w[i];
//                    queue.offer(new int[]{j,dist[j]});//将这个节点存储进去排序
//                }
//            }
//        }
//    }
}